package com.xk._03真题骗._04字符串;

import java.util.HashMap;
import java.util.Map;

/*
 * @description: https://leetcode.cn/problems/longest-substring-without-repeating-characters/
 * @author: xu
 * @date: 2022/11/2 22:24
 */
public class _3无重复字符的最长子串 {
    public int lengthOfLongestSubstring1(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int res = 0, temp = 0;
        for (int i = 0; i < s.length(); i++) {
            int j = map.getOrDefault(s.charAt(i), -1);
            map.put(s.charAt(i), i);
            temp = temp < i - j ? temp + 1 : i - j;
            res = Math.max(res, temp);
        }
        return res;
    }

    public int lengthOfLongestSubstring2(String s) {
        if(s == null || s.length() == 0) return 0;
        // 用来保存每一个字符上一次出现的位置
        Map<Character, Integer> preIndexes = new HashMap<>();
        char[] chars = s.toCharArray();
        preIndexes.put(chars[0], 0);
        // 以 i - 1 位置字符结尾的最长不重复字符串的开始索引（最左索引）
        int li = 0;
        int max = 1;
        for (int i = 1; i < chars.length; i++) {
            // i位置字符上一次出现的位置
            Integer pi = preIndexes.getOrDefault(chars[i], -1);
            if (li <= pi) {
                li = pi + 1;
            }
            // 存储这个字符出现的位置
            preIndexes.put(chars[i], i);
            // 求出最长不重复子串
            max = Math.max(max, i - li + 1);
        }
        return max;
    }

    public int lengthOfLongestSubstring3(String s) {
        if(s == null || s.length() == 0) return 0;
        // 用来保存每一个字符上一次出现的位置
        int[] words = new int[128];
        for (int i = 0; i < words.length; i++) {
            words[i] = -1;
        }
        char[] chars = s.toCharArray();
        int max = 0, temp = 0;
        for (int i = 0; i < chars.length; i++) {
            int j = words[chars[i]];
            words[chars[i]] = i;
            temp = temp < i - j ? temp + 1 : i - j;
            max = Math.max(max, temp);
        }
        return max;
    }

    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0;
        // 对照ASCII表：words 数组下标对应 ASCII码值，值为码值对应字符的上一次出现的索引位置
        int[] words = new int[128];
        for (int i = 0; i < words.length; i++) {
            words[i] = -1;
        }
        char[] chars = s.toCharArray();
        int max = 0, temp = 0;
        for (int i = 0; i < chars.length; i++) {
            int j = words[chars[i]];
            words[chars[i]] = i;
            temp = temp < i - j ? temp + 1 : i - j;
            max = Math.max(max, temp);
        }
        return max;
    }
}
